In database and other data storage systems, efficiency of accessing, retrieving, and updating data is an important feature. A database generally has a set of records stored on a computer storage device and a data access system, such as a database management system (DBMS) that includes program code and data. Generally, requests to access, retrieve, or update the data are received and processed by the data access system.
A data access system typically includes an index that enables the system to locate one or more data records. One type of index is called a B-tree. A B-tree is a tree data structure that maintains data in a sorted order, and allows searches, insertions, and deletions. In a B-tree, each node of the tree, other than leaf nodes, can have a variable number of keys and child nodes. Insertions or deletions of keys may result in changing the number of keys in one or more nodes, splitting nodes, or merging nodes. A B-tree typically has a root node, internal nodes, and leaf nodes; though a small B-tree may have no internal nodes. Typically, all leaf nodes of a B-tree are at the same depth. In a B-tree of order N, each node has at most N child nodes, and each internal node has one more key than the number of child nodes. Some B-trees may have data records, or pointers to data records, in nodes at any level of the tree. A B+ tree is a B-tree that keeps data records, or pointers to data records, only at leaf nodes.
Modern computer processors typically have one or more levels of cache memory, referred to herein simply as “cache.” A cache is a faster and smaller memory component as compared with a computer's main memory. A processor may bring small amounts of data or program instructions from the main memory into a cache, and process the data or instructions from the cache, thereby reducing access times. When the processor needs to access data from memory, it may first check whether the data has already been placed into the cache. If it has, it can access the data from the cache, without needing to take the time to access it from main memory. If not, it retrieves the data from main memory. Depending on the logic and configuration of the processor and cache, it may store the retrieved data into the cache, where it will be available for a subsequent access.
Some processors have two or three levels of cache. A level 1 (L1) cache is the smallest and fastest cache; an L2 is larger and somewhat slower cache; an L3 is still larger and slower. However, even an L3 cache is typically much faster than main memory. In some configurations, each level of cache is about an order of magnitude faster than the next level.